package com.yeung.swordoffer;


import java.util.ArrayList;

/*

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 */
public class 二叉树的下一个节点 {
    public static void main(String[] args) {

    }

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode tmp = pNode;
        ArrayList<TreeLinkNode> list = new ArrayList<>();
        //        先找到根节点
        while (pNode != null && pNode.next != null) {
            pNode = pNode.next;
        }
        //中序遍历树,记录下来
        Order(pNode, list);
        //找到指定节点的 下一个
        TreeLinkNode result = null;
        for (int i = 0; i < list.size(); i++) {
            TreeLinkNode node = list.get(i);
            if (node.val == tmp.val) {
                if (i + 1 < list.size()) result = list.get(i + 1);
            }
        }
        return result;
    }

    public void Order(TreeLinkNode root, ArrayList<TreeLinkNode> list) {
        if (root == null) return;
        Order(root.left, list);
        list.add(root);
        Order(root.right, list);
    }
}
